Leetcode第一题：两数之和（3种语言）

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的 两个 整数。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

标注：仅在Python解法做详细分析，c++与java如无特别需要注意的地方不做分析。

解法2，3参考了linfeng886的博客

分析：代码十分简单，就是首先用i在数组里循环一轮，在每个i循环下，去从剩下的元素找target-nums[i]的值。如果找到了，就return i，j两个数。（程序假设一定可以找的到） 来看看运行结果： 可以看到效率是十分低的，主要原因就是用了两个for循环，时间复杂度是O(n2)。

此代码的运行问题在于： 我们可以看到，忘记了一个元素只能用一次的规矩，因此做一个判断即可。 修改版：

可以看到：速度上升了好几倍。效果还不错。但是通过查看官方解答参考了linfeng886的博客知道还有一种更快的方法----基于hash table的解决方法。

关于hash table(哈希表)，简单来说就是存有键值对key,value的一种数据结构，对于熟悉Python的人来说，常见的字典就是一种hash table。它的查找速度是很快的，可以理解为O(1)。所以这里相当于在解法2的基础上做了一个改进。解法2 是在空间不变的前提下，在i循环时，直接在列表里查找是否含有target-nums[0]的元素，而列表的查找速度是远不如hash table。所以解法三的关键就在于，查找的任务在字典中进行而不在list中进行(有待商榷) 代码：

运行结果： 可以从代码中看到，解法3就是把需要查找的target-nums[i]从解法2中list变成了dict而已，但结果提高的十分可观。但要注意的是，这里用空间与实践做了一个tradeoff，也就说解法3虽然快了很多，但是需要的空间增加了一个新的dict。 这也给我们了一个提示：以后如遇到类似的需要遍历查找的元素时，不妨参照本例，利用hash table查找。

解法2，3参照了官方解法twosum 以及菜鸟教程java数组篇 Pythonliast与java数组区别 https://blog.csdn.net/wu1226419614/article/details/80870120 关于hashmap数据类型 https://www.cnblogs.com/hello-yz/p/3712610.html

代码：

这里不作特别说明。只想提及的是关于return new int[] {i,j}的些许解释。这种写法是官方解读给出的。参考菜鸟教程关于数组的解释，可以知道这是函数输入参数或者充当返回值的一种方式。 同时，官方解法在类的最后会throw一个异常，若将其删除会报错，因为throw也是return的一种替代形式。(就是说即使这个类在开头就说了不是void的，要返回一个int[]或者其他的东西，但是在最后抛出一个异常语法上是符合的。)对于本例，执行着就会从if下的return离开程序，所以不会抛出异常的。

在这里和Python的3种解法做一个比较。可以看到两种语言的解法1是完全相同的。但是解法2上，会有一些区别。之后解法3又是完全相同的。为什么解法2会和Python解法2有区别呢？ 先回顾下Python解法2：通过i循环列表，直接判断target - nums[i]是否在列表里，在的话，就直接返回i,与list.index(target-nums[I])。这里我们用了Python内置函数index。可以方便的获取到索引，而对于java的数组，并没有那么方便获取数组元素索引的函数。这里有一个很好的比较，从中可以知道java对于数组有一个binarySearch的查找方法，而它本身就是用二分法查找实现的，所以只适用于有序数组。同时若再用一次for循环获取索引，得不偿失。那不如多用一次for循环把索引与数值一一对应起来，用类似Python字典的方式，这样查找的更快-----hashmap 代码：

这里需要注意几点： 1.HashMap = new HshMap()这里的Integer不能用基本数据类型int。可以参看这里。 2.hashmap声明定义格式，和一般类的实例化一样。 class1 xx = new class1() 3.hashmap与hashtable。hashmap基本上可以等同于hashtable。而且可以看作为其升级版。HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。详情可查看 http://www.importnew.com/7010.html 。 4.hashmap的put,get分别为存与取。以及containsKey在代码里都有体现，很容易理解。 5.注意if判断里的&&（短路运算符）不能被&代替，可以通过LeetCode的简单试例，但是提交时会报错。分析：&即使前面为false，运算符后面的逻辑式还是会被判断。而后面的为j != map.get(a)。很可能a是不存在的，故会报错。将map.get（a）打印出来是一个null指针。进一步解释，运行用&的代码会报错： Exception in thread “main” java.lang.NullPointerException 这也就是空指针异常。解释是"程序遇上了空指针"。简单地说就是调用了未经初始化的对象或者是不存在的对象，这个错误经常出现在创建图片，调用数组这些操作中，比如图片未经初始化，或者图片创建时的路径错误等等。对数组操作中出现空指针。数组的初始化是对数组分配需要的空间，而初始化后的数组，其中的元素并没有实例化，依然是空的，所以还需要对每个元素都进行初始化（如果要调用的话)。参见 https://zhidao.baidu.com/question/494551043.html 但是，这一切在python中是允许的。

此解法思想与Python解法3如出一辙，是一模一样的，唯一区别在于Python使用字典做查找，Java使用HashMap做查找。因此本解法不做过多说明。 代码：

可以看到，与解法2相比速度提升有限。 这里需要注意的是：1.代码最后一行无论return的是什么（必须是数组）无所谓的，因为不会走到这一步的，但是最优解还是像官方解答一样抛出一个异常比较好。因为如果真走到这一步了，说明程序肯定出现了异常。 2.我这里写的和官方解法略有不同，其实是一样的。我把put进去的值换成了target-nums[i]。然后判断nums[i]是否在map中，具体就不说了，略显繁琐。

有了上述两种语言的解答做铺垫，我觉得C++解法思路就会清晰很多了。

直接看代码：

这里做一些笔记： 1.求数组长度。 Python：len(list); java:nums.length; c++:nums.size() 2.java与c++的基本数组类型长度都是不可变的，要求灵活的使用用vector代替。关于数组与vector在c++与Java中的使用 c++相关参见菜鸟教程 Java的vector参见zheting的博客 重要的一点贴出来了： java使用需要import java.util.Vector; 插入功能： public final synchronized void adddElement(Object obj) 将obj插入向量的尾部。obj可以是任何类型的对象。对同一个向量对象，亦可以在其中插入不同类的对象。但插入的应是对象而不是数值，所以插入数值时要注意将数组转换成相应的对象。 例如：要插入整数1时，不要直接调用v1.addElement(1),正确的方法为：

3.关于数组作为函数的形参。 本例中是这样写的：

或者这样写：

或者：

具体可查看菜鸟教程关于数组做形参的讲解

这里注意的是用的是c++的map实现的key,value配对。而c++中还有hash_map，即hash table。二者的区别是： hash_map采用hash表存储，map一般采用红黑树(RB Tree)实现。因此其内存数据结构是不一样的。 二者区别具体可查看 zhenyusoso的博客与Miles-的博客。 先来看map实现的代码：

做几点分析： 1.此方法和java的解法2版本是十分接近的。主要不同之处在于java的hashmap调用的方法有：put(key,value),get(key),containsKey() 而c++的map查找键值是否在为count。关于map的count与find是很常用的方法，二者用途一样。具体见Andy Niu的博客。 2.这里用的是map，为什么不用hash_map类来实现呢？我在xcode中实现了一遍，macos系统关于hash_map的声明比较特殊：

同时用find方法判别hash_map是否含有想要的key。

这个就没有什么要分析的了，和上面两种语言的解法三一模一样。

这里代码用了map的find而不是count来判断map是否含有指定key。

ps:后面的刷题笔记应该会3种语言分开记录，这样一篇文章太长，容易产生厌倦感。